package algorithm.sort;

import java.util.Arrays;

/**
 * 基数排序：适合于数字比较大的，比如手机号
 * 根据每一位的数字排序，先从后面的数字排列，再依次往前排，遇到位数不够的，可以补0来比较
 * 在实现过程中，会需要多次的计数，遍历，置换，所以需要一个2维数组来放置具体的数字分组，大小为arr[10][arr.length],
 * 每一轮遍历之后都会将之前的数值给覆盖掉，还需要一个数组专门用来放统计信息
 */
public class RadixSortTest {

    public static void main(String[] args) {
        int[] arr = {61,13,82,324,139,1,44,75,7,173};
        sort(arr);
        System.out.println("result arr = " + Arrays.toString(arr));
    }

    /**
     * 先不考虑负数
     * @param arr
     */
    public static void sort(int[] arr){
        // 确定最大位数，决定排序次数
        int maxDigit = getMaxDigit(arr);
        // 循环的过程中，进行计数排序
        // index变量用于维护将二维数组的元素写回原数组时，原数组的下标
        int index = 0;
        // 创建二维数组，用于放置每一轮数字分组情况
        int[][] temp = new int[10][arr.length];
        // 创建一个一维的统计数组用于统计个数
        int[] counting = new int[10];
        // 需要不断求每一位的数字，所以需要一个除数
        int divider = 1;
        for(int i = 0; i < maxDigit; i++){
            // 遍历数组,
            for(int j = 0; j < arr.length; j++){
                int mod = (arr[j] / divider) % 10;
                temp[mod][counting[mod]] = arr[j];
                counting[mod]++;
            }
            // 把二维数组里面的元素拿出来遍历，跟计数排序不同的是,counting数组没有将前后的元素相加，所以需要引入index来维护下标
            for(int k = 0; k < 10; k++){
                if(counting[k] > 0){
                    for(int n = 0; n < counting[k]; n++){
                        arr[index++] = temp[k][n];
                    }
                    counting[k] = 0;
                }
            }
            index = 0;
            divider *= 10;
        }
    }

    /**
     * 获取数组中的最大位数
     * @param arr
     * @return
     */
    public static int getMaxDigit(int[] arr){
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < arr.length; i++){
            int len = 0;
            int enty = arr[i];
            for(int j = enty; j > 0; j /= 10){
                len++;
            }
            if(len > max) max = len;
        }
        return max;
    }
}
